Crate colamd

Expand description

Approximate minimum degree column ordering algorithms.

colamd: an approximate minimum degree column ordering algorithm, for LU factorization of symmetric or unsymmetric matrices, QR factorization, least squares, interior point methods for linear programming problems, and other related problems.

symamd: an approximate minimum degree ordering algorithm for Cholesky factorization of symmetric matrices.

Colamd computes a permutation Q such that the Cholesky factorization of (AQ)'(AQ) has less fill-in and requires fewer floating point operations than A'A. This also provides a good ordering for sparse partial pivoting methods, P(AQ) = LU, where Q is computed prior to numerical factorization, and P is computed during numerical factorization via conventional partial pivoting with row interchanges.

Symamd computes a permutation P of a symmetric matrix A such that the Cholesky factorization of PAP' has less fill-in and requires fewer floating point operations than A. Symamd constructs a matrix M such that M'M has the same nonzero pattern of A, and then orders the columns of M using colmmd. The column ordering of M is then returned as the row and column ordering P of A.

The authors of the code itself are Stefan I. Larimore and Timothy A. Davis (davis at cise.ufl.edu), University of Florida. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory.

This work was supported by the National Science Foundation, under grants DMS-9504974 and DMS-9803599.

Constants

AGGRESSIVE

Aggressive absorption.

DEFRAG_COUNT

Memory defragmentation count output statistic.

DENSE_COL

Dense column knob and output statistic.

DENSE_ROW

Dense row knob and output statistic.

ERROR_A_TOO_SMALL

ERROR_COL_LENGTH_NEGATIVE

ERROR_ROW_INDEX_OUT_OF_BOUNDS

INFO1

Error info, or info on jumbled columns.

INFO2

INFO3

KNOBS

Size of the knobs[] array. Only knobs[0..1] are currently used.

OK

OK_BUT_JUMBLED

STATS

Number of output statistics. Only stats[0..6] are currently used.

STATUS

Zero OK, > 0 warning or notice, < 0 error.

Functions

colamd

Computes a column ordering Q of a sparse matrix A such that the LU factorization P(AQ) = LU remains sparse, where P is selected via partial pivoting. The routine can also be viewed as providing a permutation Q such that the Cholesky factorization (AQ)'(AQ) = LL' remains sparse.

colamd_report

Print colamd statistics to standard output.

default_knobs

Returns the default values of the user-controllable parameters for colamd and symamd.

recommended

Recommended returns the suggested size for a_len.

symamd

Computes an ordering P of a symmetric sparse matrix A such that the Cholesky factorization PAP' = LL' remains sparse.

symamd_report

Print symamd statistics to standard output.

Type Definitions

Int